package wxy;

import java.util.ArrayDeque;
import java.util.Deque;

public class LeetCode503 {
    public int[] nextGreaterElements(int[] nums) {
        int length = nums.length;
        int[] res = new int[length];
        for (int i = 0; i < length; i++) {
            res[i] = -1;
        }
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < 2 * length; i++) {
            while (!deque.isEmpty() && nums[i % length] > nums[deque.peek()]) {
                Integer idx = deque.pop();
                res[idx] = nums[i % length];
            }
            deque.push(i % length);
        }
        return res;
    }
}
